package test3;

import jdk.internal.org.objectweb.asm.util.TraceAnnotationVisitor;

import java.util.*;

public class Solution3 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int value = 0;

    public TreeNode convertBST(TreeNode root) {
        // 在此处写入代码
        TreeNode newRoot = new TreeNode(0);
        add(root, newRoot, 0);
        return newRoot;
    }


    public int add(TreeNode root, TreeNode newNode, int initValue) {

        if (root == null) {
            return initValue;
        }

        TreeNode newRight = null;
        TreeNode newLeft = null;
        if (root.right != null) {
            newRight = new TreeNode(0);
            newNode.right = newRight;
        }
        if (root.left != null) {
            newLeft = new TreeNode(0);
            newNode.left = newLeft;
        }
        int right = add(root.right, newNode.right, initValue);
        newNode.val =  right + root.val;
        int left = add(root.left, newNode.left, newNode.val);

        return Math.max(left, newNode.val);
    }

    int sum = 0;
    public TreeNode convertBST2(TreeNode root) {
        // 在此处写入代码
        if (root == null) {
            return null;
        }

        TreeNode right = convertBST2(root.right);
        if (right != null) {
            root.val = right.val + root.val + sum;
        }
        sum = root.val;
        convertBST2(root.left);
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        // 在此处写入代码
        if (root == null) {
            return null;
        }
        TreeNode n = root;
        TreeNode pre = null;
        boolean isLeft = true;
        while(n != null ) {
            if (n.val == key) {
                if (n.left == null && n.right == null) {
                    if (pre == null) {
                        return null;
                    }
                    if (isLeft) {
                        pre.left = null;
                    } else {
                        pre.right = null;
                    }
                    return  root;
                }
                TreeNode node = n;
                if (n.left == null) {
                    n = n.right;
                } else {
                    n = n.left;
                    TreeNode right = node.right;
                    node = n;
                    while (node.right != null) {
                        node = node.right;
                    }
                    node.right = right;
                }

                if (pre == null) {
                    root = n;
                } else {
                    if (isLeft) {
                        pre.left = n;
                    } else {
                        pre.right = n;
                    }
                }
            }
            if (n.val < key) {
                pre = n;
                n = n.right;
                isLeft = false;
            }
            if (n.val > key) {
                pre = n;
                n = n.left;
                isLeft = true;
            }
        }

        return root;

    }



    public TreeNode deleteNode2(TreeNode root, int key) {
        delete(root, null, true, key);
        return root;
    }

    TreeNode min = null;
    public void delete(TreeNode root, TreeNode pre, boolean isLeft, int key) {
        if (root == null) {
            return;
        }
        if (root.val > key) {
            delete(root.left, root, true, key);
        }
        if (root.val < key) {
            delete(root.right, root, false, key);
        }

        if (root.val == key) {
            TreeNode node = root;
            root = root.left == null ? root.right : root.left;
            if (pre == null) {
                delete(root, null, isLeft, key);
                return;
            }
            if (isLeft) {
                pre.left = root;
            } else {
                pre.right = root;
            }
            delete(root, pre, isLeft, key);
        }
    }

    // Encodes a tree to a single string.
    String result = "";
    public String serialize(TreeNode root) {
        if (root == null) return "";
        result = serialize(root.left) + "," + root.val + "," + serialize(root.right) + ",";
        return result;
    }

    public static String serialize2(TreeNode root) {
        if (root == null) return "";
        StringBuilder  res = new StringBuilder();
        LinkedList<TreeNode> list = new LinkedList<>();
        list.push(root);
        boolean isOver = false;
        while (!isOver) {
            isOver = true;
            int size = list.size();
            while (size > 0) {
                TreeNode current = list.pollFirst();
                if (current == null) {
                    res.append(",");
                } else {
                    res.append(current.val + ",");
                    list.add(current.left);
                    list.add(current.right);
                    isOver = false;
                }
                size--;
            }

        }
        return res.substring(0, res.length()-1);
    }

    public static TreeNode deserialize(String data) {
        if(data.isEmpty()) {
            return null;
        }
        String[] array = data.split(",");
        LinkedList<TreeNode> list = new LinkedList<>();
        int index = 1;
        TreeNode root = getNode(array[0]);
        list.push(root);
        while (index < array.length) {
            System.out.println(array[index]);
            TreeNode node = list.pollFirst();
            if (node == null) {
                continue;
            }
            node.left = getNode(array[index++]);
            list.add(node.left);
            if(index < array.length) {
                node.right = getNode(array[index++]);
                list.add(node.right);
            }

        }
        return root;
    }

    public static TreeNode getNode(String c) {
        if ("".equals(c)) {
            return null;
        }
        return new TreeNode(Integer.parseInt(c));
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
//        TreeNode root = null;
        /*root.left = new TreeNode(1);
        root.right = new TreeNode(3);*/
        String res = serialize2(root);
        System.out.println(res);
        deserialize(res);
    }

    int num = 0;


    public void countSmaller(int[] nums, int[] res, int index) {

        if (index >= nums.length) {
            res[index] = 0;
        }

        int v = nums[index];
        countSmaller(nums, res, index++);
        if (index > 0) {


        }

    }

    //使用树状数组
    class Solution {
        private int[] c;
        private int[] a;

        public List<Integer> countSmaller(int[] nums) {
            List<Integer> resultList = new ArrayList<Integer>();
            discretization(nums);
            init(nums.length + 5);
            for (int i = nums.length - 1; i >= 0; --i) {
                int id = getId(nums[i]);
                resultList.add(query(id - 1));
                update(id);
            }
            Collections.reverse(resultList);
            return resultList;
        }

        private void init(int length) {
            c = new int[length];
            Arrays.fill(c, 0);
        }

        private int lowBit(int x) {
            return x & (-x);
        }

        private void update(int pos) {
            while (pos < c.length) {
                c[pos] += 1;
                pos += lowBit(pos);
            }
        }

        private int query(int pos) {
            int ret = 0;
            while (pos > 0) {
                ret += c[pos];
                pos -= lowBit(pos);
            }

            return ret;
        }

        private void discretization(int[] nums) {
            Set<Integer> set = new HashSet<Integer>();
            for (int num : nums) {
                set.add(num);
            }
            int size = set.size();
            a = new int[size];
            int index = 0;
            for (int num : set) {
                a[index++] = num;
            }
            Arrays.sort(a);
        }

        private int getId(int x) {
            return Arrays.binarySearch(a, x) + 1;
        }
    }


}